package 图.最短路径;

import 抽象数据类型.DirectedEdge;
import 抽象数据类型.EdgeWeightedGraph;

/**
 * @description:
 * @author: ywk
 * @date: 2021-08-23
 */
public class 货币兑换中的套汇 {
    public static void main(String[] args) {
        int[] arr1 = {0, 1, 2, 0, 2, 1};
        int[] arr2 = {1, 2, 0, 2, 1, 0};
        double[] weight = {1.366, 0.955, 0.741, 1.349, 1.005, 0.732};
        for (int i = 0; i < weight.length; i++) {
            weight[i] = -Math.log(weight[i]);
        }
        EdgeWeightedGraph G = new EdgeWeightedGraph(3);
        G.addGraph(arr1, arr2, weight);
        基于队列的BellmanFord算法.BellmanFOrdSP sp = new 基于队列的BellmanFord算法.BellmanFOrdSP(G, 0);
        if (sp.hasNegativeCycle()) {
            double stake = 1000.0;
            for (DirectedEdge e : sp.negativeCycle()) {
                System.out.println(String.format("%10.5f %s", stake, e.from()));
                stake *= Math.exp(-e.weight());
                System.out.println(String.format("=%10.5f %s", stake, e.to()));
            }
        }

    }
}
